package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
https://leetcode.cn/problems/non-decreasing-subsequences/description/

491. 非递减子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
 */
class leetcode_491 {
    @Test
    fun test_1() {
        val actual = findSubsequences(intArrayOf(4, 6, 7, 7))
        val expect = arrayListOf(
            arrayListOf(4, 6), arrayListOf(4, 6, 7), arrayListOf(4, 6, 7, 7), arrayListOf(4, 7), arrayListOf(4, 7, 7), arrayListOf(6, 7), arrayListOf(6, 7, 7), arrayListOf(7, 7)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = findSubsequences(intArrayOf(4, 4, 3, 2, 1))
        val expect = arrayListOf(arrayListOf(4, 4))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun findSubsequences(nums: IntArray): List<List<Int>> {
        /*
        回溯法
        1 求递增子序列，所以不能排序，因此不能使用used数组来去重，而是使用函数内部的set去重复
        2 size 至少是个元素的子集问题
        3 递增
         */
        val path: ArrayList<Int> = ArrayList()
        val result: ArrayList<ArrayList<Int>> = ArrayList()
        backtacking(nums, 0, path, result)
        return result
    }

    private fun backtacking(nums: IntArray, startIndex: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>) {
        // 1 确认函数参数以及返回值
        // println("startIndex[0] = ${startIndex}")
        // 2 确认终止条件
        // 结束条件
        if (nums.size < 2) {
            return
        }
        // start 已经到 数组 之外了
        if (startIndex > nums.size) {
            return
        }
        // 收集结果
        // 子序列至少有2个元素才收集
        if (path.size >= 2) {
            val t: ArrayList<Int> = ArrayList<Int>()
            t.addAll(path)
            result.add(t)
        }

        // 3 单层循环 [start, size)
        val set: HashSet<Int> = HashSet<Int>() // 使用局部Set对树层进行去重
        for (i in startIndex until nums.size) { // [startIndex, size)
            // println("nums[i] = ${nums[i]}")
            // 处理节点

            // 树层去重
            // if(i > 1 && (nums[i] == nums[i-1]) && set.contains(nums[i-1]) == false ){ // Not OK: 去多了
            if (set.contains(nums[i])) {
                continue
            }
            // 过滤不递增
            if (path.size > 0 && path[path.size - 1] > nums[i]) {
                continue
            }
            path.add(nums[i])
            set.add(nums[i])
            // println("path = ${path.toString()}")

            // 递归
            backtacking(nums, i + 1, path, result)

            // 回溯
            path.removeAt(path.size - 1)
            // 4 剪枝:not need
            // 5 去重：树层 ： hashset,done

        }
    }
}